package practice_2025_9.practice_9_16;

class Solution {
    /**
     * 分汤
     */
    double[][] f = new double[200][200];
    public double soupServings(int n) {
        // 两种汤 A + B, 初始均为 n
        // 每一轮随机4选1
        // 返回 A 在 B 前取完的概率 + 两种汤在同一回合取完的概率
        // 100  0
        // 75  25
        // 50  50
        // 25  75
        // dfs + 记忆化搜索
        return n > 5000 ? 1: dfs((n + 24) / 25, (n + 24) / 25);
    }
    public double dfs(int A, int B) {
        // 同时取完 -> 概率的一半
        if (A <= 0 && B <= 0) {
            return 0.5;
        }
        // A 取完 -> 1
        if (A <= 0) {
            return 1.0;
        } 
        // B 取完 -> 0
        if (B <= 0) {
            return 0;
        }
        // 是否有记录
        if (f[A][B] > 0) {
            return f[A][B];
        }
        double res = 0.25 * ((dfs(A - 4, B)) + dfs(A - 3, B - 1) + dfs(A - 2, B - 2) + dfs(A - 1, B - 3));
        f[A][B] = res;
        return res;
    }

    /**
     * 知道秘密的人
     * @param n
     * @param delay
     * @param forget
     * @return
     */
    public int peopleAwareOfSecret(int n, int delay, int forget) {
        // 第 1 天, 一个人发现了一个秘密
        // 人 会在 delay 天之后, 每天给一个新人分享密码
        // 人 会在 forget 天之后，忘记这个密码
        // 计算 n 天后, 知道密码的人
        // f[i]: 第 i 天知道总人数
        // g[i]: 第 i 天新知道的人数（当天新知道 = 当天分享人数）
        // 第 i 天知道的总人数 = f[i] + g[i]
        // g[i] = 昨天分享的人数 + 前 delay 天新知道的人数 - 前 forget 天知道的人数
        //      = g[i - 1] + g[i - delay] - g[i - forget]
        // f[i] = 昨天知道总人数 + 今天新知道人数 - 前 forget 天知道人数
        //      = f[i] + g[i] - g[i - forget]
        int MOD = 1000000007;
        long[] f = new long[n];
        long[] g = new long[n];
        for(int i = 0; i < delay; i++) {
            f[i] = 1;
        }
        g[0] = 1;
        g[delay] = 1;
        f[delay] = 2;
        for(int i = delay + 1; i < n; i++) {
            if (i - forget >= 0) {
                g[i] = ((g[i - 1] + g[i - delay]) - g[i - forget] + MOD) % MOD;
                f[i] = ((f[i - 1] + g[i]) - g[i - forget] + MOD) % MOD;
            } else {
                g[i] = g[i - 1]  + g[i - delay];
                f[i] = f[i - 1]  + g[i];
            }
            g[i] %= MOD;
            f[i] %= MOD;
        }
        // System.out.println(Arrays.toString(f));
        // System.out.println(Arrays.toString(g));
        return (int)f[n - 1];

    }
}